A recurring problem in data and file storage systems such as a database, in particular those implemented in computer systems, is the search for and location of specific items of information stored in the database. Such searches are generally accomplished by constructing a directory, or index, to the database, and using search keys to search through the index to find pointers to the most likely locations of the information in the database, whether that location is within the memory or the storage medium of the computer.
In its most usual forms, an index to database records within a computer is structured as a tree comprised of one or more nodes, connected by branches, which is stored within a storage means of the computer. Each node generally includes one or more branch fields containing information for directing a search, and each such branch field usually contains a pointer, or branch, to another node, and an associated branch key indicating ranges or types of information that may be located along that branch from the node. The tree, and any search of the tree, begins at a single node referred to as the root node and progresses downwards through the various branch nodes until the nodes containing either the items of information or, more usually, pointers to items of information are reached. The information related nodes are often referred to as leaf nodes or, since this is the level at which the search either succeeds or fails, failure nodes. Within a tree storage structure of a computer, any node within a tree is a parent node with respect to all nodes dependent from that node, and sub-structures within a tree which are dependent from that parent node are often referred to as subtrees with respect to that node.
The decision as to which direction, or branch, to take through a tree storage structure in a search is determined by comparing the search key and the branch keys stored in each node encountered in the search. The results of the comparisons to the branches depending from a given node are to be followed in the next step of the search. In this regard, search keys are most generally comprised of strings of characters or numbers which relate to the item or items of information to be searched for within the computer system.
The prior art contains a variety of search tree data storage structures for computer database systems, among which is the apparent ancestor from which all later tree structures have been developed and the most general form of search tree well known in the art, the "B-tree." (See, for example, Knuth, The Art of Computer Programming, Vol. 3, pp. 473-479). A B-tree provides both satisfactory primary access and good secondary access to a data set. Therefore, these trees naturally tend to be used in data storage structure often utilized by database and file systems. Nevertheless, there are problems that exist with the utilization of B-tree storage structures within database systems. Every indexed attribute value must be replicated in the index itself. The cumulative effect of replicating many secondary index values is to create indices which often exceed the size of the database itself. This overhead can force database designers to reject potentially useful access paths. Moreover, inclusion of search key values within blocks of the B-tree significantly decreases the block fan out and increases tree depth and retrieval time.
Another tree structure which can be implemented in computer database systems, compact 0-complete trees (i.e., C.sub.0 -trees), eliminates search values from indices by replacing them with small surrogates whose typical 8-bit length will be adequate for most practical key lengths (i.e., less than 32 bytes). Thus, actual values can be stored anywhere in arbitrary order, leaving the indices to the tree structure to be just hierarchical collections of (surrogate, pointer) pairs stored in an index block. This organization can reduce the size of the indexes by about 50% to 80% and increases the branching factor of the trees, which provides a reduction in the number of disk accesses in the system per exact match query within computer database systems. (See Orlandic and Pfaltz, Compact 0-Complete Trees, Proceedings of the 14th VLDB Conference, pp. 372-381.)
While the known method of creating C.sub.0 -trees increases storage utilization 50% to 80% over B-trees, there is a waste of storage space due to the presence of dummy entries (surrogate, pointer==NIL) wherein the number of index entries at the lowest level of the tree exceeds the actual number of records stored. Therefore, the expected storage utilization of index entries of C.sub.0 -trees at the lowest tree level is 0.567 versus 0.693 as in the case of B-trees.
Moreover, although B-trees and C.sub.0 -tree storage structures represent efficient methods of searching for values, both methods require initial generation of the tree data storage structure itself. Neither of these computer storage structures inherently stores information in sorted order.
A tree can be built more efficiently if the key records are initially sorted in the order of their key field, than if records are in random order. Therefore, an efficient computer database system should sort sets of keys first, and then build a tree based on keys extracted at intervals from the sorted keys.
If the values are in sorted ordered, the next key value to be stored is likely within the range of key values for the current leaf index block or subtree. In addition, index block splitting can be deferred until all keys within a given key interval of the current index block are inserted. Therefore, a goal is to build a data storage structure and method which effectively inputs an ordered sort of key records or data items within a key range interval in the most efficient way possible. In particular, the data storage structure and method should reduce wasted storage space and, during input, sort the search keys that access the data items stored within the storage medium or memory of the computer. This goal is to be achieved while simultaneously retaining the merits and taking advantage of the properties of known B-tree and C.sub.0 -tree computer storage structures.